#ifndef LEETCODE_CN_CPP_PROBLEMS_22_H
#define LEETCODE_CN_CPP_PROBLEMS_22_H

#include <string>
#include <unordered_set>
#include <vector>

using namespace std;

namespace problem_22
{

class Solution
{
public:
    vector<string> generateParenthesis(int n)
    {
        if (n == 0)
        {
            return {};
        }
        else if (n == 1)
        {
            return {"()"};
        }
        else
        {
            unordered_set<string> result;
            auto tmp = generateParenthesis(n - 1);
            for (auto &i : tmp)
            {
                result.insert(move("()" + i));
                result.insert(move(i + "()"));
                result.insert(move("(" + i + ")"));
            }
            if (n > 3)
            {
                for (int i = 2; i <= n / 2; i++)
                {
                    auto tmp1 = generateParenthesis(n - i);
                    auto tmp2 = generateParenthesis(i);
                    for (auto &a : tmp1)
                    {
                        for (auto &b : tmp2)
                        {
                            result.insert(move(a + b));
                            result.insert(move(b + a));
                        }
                    }
                }
            }
            vector<string> res;
            res.reserve(result.size());
            for (auto &str : result)
            {
                res.push_back(move(str));
            }
            return move(res);
        }
    }
};

} // namespace problem_22

#endif //LEETCODE_CN_CPP_PROBLEMS_22_H
